package com.learn.algorithm.graph;

import java.util.PriorityQueue;

public class LeetCode778 {
    public static int swimInWater(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }

        distance[0][0] = grid[0][0];
        boolean[][] visited = new boolean[n][m];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        heap.add(new int[]{0, 0, grid[0][0]});

        while (!heap.isEmpty()) {
            int x = heap.peek()[0];
            int y = heap.peek()[1];
            int c = heap.peek()[2];
            heap.poll();

            if (visited[x][y]) {
                continue;
            }
            visited[x][y] = true;
            // 找到了终点
            if (x == n - 1 && y == m - 1) {
                return c;
            }

            Move.forEachMove(x, y, n, m, new Move.Moved() {
                @Override
                public void to(int toX, int toY) {
                    if (!visited[toX][toY]) {
                        int nc = Math.max(c, grid[toX][toY]);
                        if (nc < distance[toX][toY]) {
                            distance[toX][toY] = nc;
                            heap.add(new int[]{toX, toY, nc});
                        }
                    }
                }
            });
        }

        return -1;
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{{0, 2}, {1, 3}};
        System.out.println(swimInWater(grid));
    }
}
